/*
Hdu1075
Sample Input
START
from fiwo
hello difh
mars riwosf
earth fnnvk
like fiiwj
END
START
difh, i'm fiwo riwosf.
i fiiwj fnnvk!
END
 

Sample Output
hello, i'm from mars.
i like earth!
 */
package com.yuan.algorithms.team20150724;

import java.util.Scanner;
class DictionaryTree {
	private int SIZE = 26;
	private DicNode root;
	
	public DictionaryTree() {
		root = new DicNode();
	}
	private class DicNode {
		private DicNode[] son;//保存子节点的数组
		private char key;//检索的字符值
		private String val;//存储对应索引的值
		private boolean isEnd;//是否为最后一个节点
		
		public DicNode() {
			son = new DicNode[SIZE];
			val = null;
			isEnd = false;
		}
	}
	
	/**
	 * 向字典树中插入单词和其对应值
	 * @param str 单词
	 * @param val 值
	 */
	public void insert(String str, String val) {
		if (str == null || str.length() == 0) {
			return;
		}
		DicNode node = root;
		char[] key = str.toCharArray();
		for (int i = 0, len = key.length; i < len; i++) {
			int index = key[i] - 'a';
			if (node.son[index]==null) {
				node.son[index] = new DicNode();
			}
			node.son[index].key = key[i];
			node = node.son[index];
		}
		node.isEnd = true;
		node.val = val;
	}
	
	/**
	 * 搜索指定字符串在字典树中对应的单词，如果没有搜索到，则返回原字符串
	 * @param str
	 * @return
	 */
	public String search(String str) {
		String result = str;
		DicNode node = root;
		char[] data = str.toCharArray();
		for (int i = 0, len = data.length; i < len; i++) {
			int index = data[i] - 'a';
			if (node.son[index] == null) {
				return result;
			} else {
				node = node.son[index];
			}
		}
		return node.isEnd ? node.val : result;
	}
}

public class 字典树_火星文翻译成英文 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		DictionaryTree tree = new DictionaryTree();
		sc.next();//接收START
		String strVal, strKey;
		while (!(strVal = sc.next()).equals("END")) {
			strKey = sc.next();
			tree.insert(strKey, strVal);
		}
		sc.next();//接收START
		sc.nextLine();//接收多余的换行符
		String word;
		while (!(word = sc.nextLine()).equals("END")) {
			String temp = "";
			for (int i = 0, len = word.length(); i < len; i++) {
				char t = word.charAt(i);
				if (t >= 'a' && t <= 'z') {
					temp += t;
					if (i == len - 1) {
						System.out.print(search(tree, temp));
					}
				} else {
					System.out.print(search(tree, temp) + t);
					temp = "";
				}
			}
			System.out.println();
		}
	}

	private static String search(DictionaryTree tree, String temp) {
		return tree.search(temp);
	}

}
